/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package map.maps;

import BothSide.Constants;


/**
 *
 * @author DeLac
 */
public class MapPaths
 {
   WeightedGraph grafo;
   String ostacoli;
   int colonne; //i
   int righe;  //j

/*int i, intj, String ostacoli**/
   public MapPaths(String ostacoli){
      this.colonne = Constants.colonne;
      this.righe = Constants.righe;
      grafo = new WeightedGraph(righe*colonne);
      this.ostacoli = ostacoli;
      caricaEdges(ostacoli);
   }

private void caricaEdges(String ostacoli)
  {
      for(int i=0; i<colonne; i++)
          {
            for (int j=0; j<righe; j++)
               {
                int current = j+(i*righe);
                grafo.setLabel (current, ""+current);
                if( ostacoli.charAt(current) == "0".charAt(0))
                    {
    /*sud est*/      if (current<(Constants.righe*(Constants.colonne-1))&& current%Constants.righe!=Constants.righe-1 &&current%Constants.righe!=Constants.righe-2&& ostacoli.charAt((current+1)  ) == "0".charAt(0))
                         {grafo.addEdge(current, ((current+1)), 2);
                         }
    /*nord est*/     if (current<(Constants.righe*(Constants.colonne-1)) && current%Constants.righe!=0&&current%Constants.righe!=1 && ostacoli.charAt((current-1)  ) == "0".charAt(0))
                         {grafo.addEdge(current, ((current-1)), 2);
                         }
    /*nord*/         if (current%Constants.righe!=0&&current%Constants.righe!=1 && ostacoli.charAt(current -2  ) == "0".charAt(0))
                         {grafo.addEdge(current, current-2, 3);
                         }
    /*sud*/          if ( (current%Constants.righe)!=Constants.righe-1 &&current%Constants.righe!=Constants.righe-2 && ostacoli.charAt(current+2) == "0".charAt(0))
                         {grafo.addEdge(current, current+2, 3);
                         }
    /*nord ovest*/   if (current>Constants.righe && current%Constants.righe!=0 &&current%Constants.righe!=1&& ostacoli.charAt(current -1 - Constants.righe  ) == "0".charAt(0))
                         {grafo.addEdge(current, current -1 - Constants.righe, 2);
                         }
    /*sud ovest*/    if (current>Constants.righe && current%Constants.righe!=Constants.righe-1 &&current%Constants.righe!=Constants.righe-2 &&  ostacoli.charAt(current +2 - Constants.righe  ) == "0".charAt(0))
                         {grafo.addEdge(current, current +2 - Constants.righe, 2);
                         }
    /* ovest*/       if (current>Constants.righe &&  ostacoli.charAt(current - Constants.righe  ) == "0".charAt(0))
                         {grafo.addEdge(current, current - Constants.righe, 3);
                         }
    /*est    */      if (current<(Constants.righe*(Constants.colonne-1)) &&  ostacoli.charAt(current + Constants.righe  ) == "0".charAt(0))
                         {grafo.addEdge(current, current +Constants.righe, 3);
                         }
                    }
               }
          }
   }



   public java.util.ArrayList<String> calcolaPath(int start, int end){
      final int [] pred = dijkstra (grafo, start);
	 printPath (grafo, pred, start, end);
         return getPath (grafo, pred, start, end);
   }
  

// Dijkstra's algorithm to find shortest path from s to all other nodes
   private static int [] dijkstra (WeightedGraph G, int s) {
      final int [] dist = new int [G.size()];  // shortest known distance from "s"
      final int [] pred = new int [G.size()];  // preceeding node in path
      final boolean [] visited = new boolean [G.size()]; // all false initially

      for (int i=0; i<dist.length; i++) {
	 dist[i] = Integer.MAX_VALUE;
      }
      dist[s] = 0;

      for (int i=0; i<dist.length; i++) {
	 final int next = minVertex (dist, visited);
	 if(next>=0)
         {
          visited[next] = true;

	 // The shortest path to next is dist[next] and via pred[next].

	 final int [] n = G.neighbors (next);
	 for (int j=0; j<n.length; j++) {
	    final int v = n[j];
	    final int d = dist[next] + G.getWeight(next,v);
	    if (dist[v] > d) {
	       dist[v] = d;
	       pred[v] = next;
	    }
	 }
      }}
      return pred;  // (ignore pred[s]==0!)
   }

   private static int minVertex (int [] dist, boolean [] v) {
      int x = Integer.MAX_VALUE;
      int y = -1;   // graph not connected, or no unvisited vertices
      for (int i=0; i<dist.length; i++) {
	 if (!v[i] && dist[i]<x) {y=i; x=dist[i];}
      }
      return y;
   }

    private void printPath (WeightedGraph G, int [] pred, int s, int e) {
      final java.util.ArrayList path = new java.util.ArrayList();
      int x = e;
      while (x!=s) {
	 path.add (0, G.getLabel(x));
	 x = pred[x];
      }
      path.add (0, G.getLabel(s));
      System.out.println (path);
   }

    private  java.util.ArrayList<String> getPath (WeightedGraph G, int [] pred, int s, int e) {
      final java.util.ArrayList path = new java.util.ArrayList();
      int x = e;
      while (x!=s) {
	 path.add (0, G.getLabel(x));
	 x = pred[x];
      }
      path.add (0, G.getLabel(s));
      return (path);
   }




public int getRombo(int x, int y)
  {
  int n_rombo=-1;
  int altezza =Constants.ALTEZZArOMBO;
  int larghezza = Constants.LARGHEZZArOMBO;
  int quadrato = ((x/larghezza)*Constants.righe/2)+(y/altezza);
  // cerco quale sotto-quadrato
  if (x > larghezza*(x/larghezza) +larghezza/2)
      {//meta' a destra
        if(y < altezza*(y/altezza) +altezza/2)
            { //meta' sopra
               double y_latoM = (altezza*(y/altezza))+altezza/2;
               double x_diagonale = x - ((larghezza*(x/larghezza))+larghezza/2);
               double pezzetto_diagonale = ((Math.sqrt((altezza/2*altezza/2)+(larghezza/2*larghezza/2)))/(larghezza/2))*x_diagonale;
               double puntoDiagonale = (y_latoM)     -   (Math.sqrt(-(x_diagonale*x_diagonale)+(pezzetto_diagonale*pezzetto_diagonale)) /** (x_diagonale)*/);
               if (y < puntoDiagonale)
                   { // sopra diagonale
                    n_rombo = (quadrato*2)-1;
                   }
               else{ // sotto diagonale
                    n_rombo = (quadrato*2)+Constants.righe;
                   }
            }
        else
            { //meta' sotto
             double y_latoM = (altezza*(y/altezza))+altezza/2;
               double x_diagonale = x - ((larghezza*(x/larghezza))+larghezza/2);
               double pezzetto_diagonale = ((Math.sqrt((altezza/2*altezza/2)+(larghezza/2*larghezza/2)))/(larghezza/2))*x_diagonale;
               double puntoDiagonale = (y_latoM)     +   (Math.sqrt(-(x_diagonale*x_diagonale)+(pezzetto_diagonale*pezzetto_diagonale)) /** (x_diagonale)*/);
             if (y < puntoDiagonale)
                   { // sopra diagonale
                    n_rombo = (quadrato*2)+Constants.righe;
                   }
               else{ // sotto diagonale
                    n_rombo = (quadrato*2)+1;
                   }
            }
      }
  else
      {//meta' a sinistra
       if(y < altezza*(y/altezza) +altezza/2)
            { //meta' sopra
               double y_latoM = (altezza*(y/altezza))+altezza/2;
               double x_diagonale = x - ((larghezza*(x/larghezza)))-(larghezza/2);
               double pezzetto_diagonale = ((Math.sqrt((altezza/2*altezza/2)+(larghezza/2*larghezza/2)))/(larghezza/2))*x_diagonale;
               double puntoDiagonale = (y_latoM)     -   (Math.sqrt(-(x_diagonale*x_diagonale)+(pezzetto_diagonale*pezzetto_diagonale)) /** (x_diagonale)*/);
               if (y < puntoDiagonale)
                   { // sopra diagonale
                    n_rombo = quadrato*2-1;
                   }
               else{ // sotto diagonale
                    n_rombo = quadrato*2;
                   }
            }
        else
            { //meta' sotto
           double y_latoM = (altezza*(y/altezza))+altezza/2;
               double x_diagonale = x - ((larghezza*(x/larghezza)))-(larghezza/2);
               double pezzetto_diagonale = ((Math.sqrt((altezza/2*altezza/2)+(larghezza/2*larghezza/2)))/(larghezza/2))*x_diagonale;
               double puntoDiagonale = (y_latoM)     +   (Math.sqrt(-(x_diagonale*x_diagonale)+(pezzetto_diagonale*pezzetto_diagonale)) /** (x_diagonale)*/);
             if (y < puntoDiagonale)
                   { // sopra diagonale
                    n_rombo = quadrato*2;
                   }
               else{ // sotto diagonale
                    n_rombo = quadrato*2+1;
                   }
            }
      }
   return n_rombo;
  }








private class WeightedGraph {

   private int [][]  edges;  // adjacency matrix
   private Object [] labels;

   public WeightedGraph (int n) {
      edges  = new int [n][n];
      labels = new Object[n];
   }


   public int size() { return labels.length; }

   public void   setLabel (int vertex, Object label) { labels[vertex]=label; }
   public Object getLabel (int vertex)               { return labels[vertex]; }

   public void    addEdge    (int source, int target, int w)  { edges[source][target] = w; }
   public boolean isEdge     (int source, int target)  { return edges[source][target]>0; }
   public void    removeEdge (int source, int target)  { edges[source][target] = 0; }
   public int     getWeight  (int source, int target)  { return edges[source][target]; }

   public int [] neighbors (int vertex) {
      int count = 0;
      for (int i=0; i<edges[vertex].length; i++) {
	 if (edges[vertex][i]>0) count++;
      }
      final int[]answer= new int[count];
      count = 0;
      for (int i=0; i<edges[vertex].length; i++) {
	 if (edges[vertex][i]>0) answer[count++]=i;
      }
      return answer;
   }

   public void print () {
      for (int j=0; j<edges.length; j++) {
	 System.out.print (labels[j]+": ");
	 for (int i=0; i<edges[j].length; i++) {
	    if (edges[j][i]>0) System.out.print (labels[i]+":"+edges[j][i]+" ");
	 }
	 System.out.println ();
      }
   }



}
 }
